package hydrap2p.helper;

import hydrap2p.library.Range;

import java.util.LinkedList;
import java.util.List;

public class RangeUtils {

	/**
	 * Merges this new Range into this other list of Ranges
	 * Automatically merges adjacent or overlapping ranges
	 * It assumes that the list is sorted, and it returns a sorted list
	 * @param list
	 * @param other
	 * @return
	 */
	public static List<Range> merge(List<Range> list, Range other)
	{
		List<Range> ret=new LinkedList<Range>();
		for (int i=0; i<list.size(); i++)
		{
			Range cur=list.get(i);
			Range temp=new Range();
			
			if (other==null)
			{
				temp.setStart(cur.start);
				temp.setLen(cur.len);
				ret.add(temp);
			}
			else if (cur.start==other.start)
			{
				temp.setStart(cur.start);
				temp.setLen(Math.max(cur.len, other.len));
				ret.add(temp);
				// other is being eaten, so we can delete it
				other=null;
			}
			else
			{
				Range first=null;
				Range second=null;
				// figure out which Range has the first start
				if (cur.start<other.start)
				{
					first=cur;
					second=other;
				}
				else if (other.start<cur.start)
				{
					first=other;
					second=cur;
				}

				// find each end
				long firstend=first.start+first.len;
				long secondend=second.start+second.len;
				
				if (firstend<second.start)	// the ranges don't touch
				{
					temp.setStart(first.start);
					temp.setLen(first.len);
					ret.add(temp);
					
					if (first==other)		// we inserted Other before Cur, so now add Cur since we won't see it again
					{
						other=null;
						
						temp=new Range();
						temp.setStart(cur.start);
						temp.setLen(cur.len);
						ret.add(temp);
						
					}
					
				}
				else if (firstend>=second.start)		// overlapping
				{
					if (i<list.size()-1)
					{
						Range third=list.get(i+1);
						long thirdend=third.start+third.len;
						if (secondend>=third.start)		// if the second element overlaps the third element (Other overlaps the next) merge them
						{
							temp.setStart(first.start);
							temp.setLen(thirdend);
							other=null;		// don't process other, since we've included it
							i++;		// don't process third on next loop, because it's already included
						}
					}
					
					if (other!=null)
					{
						temp.setStart(first.start);
						temp.setLen(Math.max(firstend,secondend)-first.start);
						other=null;
					}
					
					ret.add(temp);
				}
				else
					System.err.println("RangeUtils.java: merge() went wrong!!");
				
				
			}	
		}
		if (other!=null)
		{
			Range temp=new Range();
			temp.setStart(other.start);
			temp.setLen(other.len);
			ret.add(temp);
		}
		return ret;
	}
	
	/**
	 * Determines whether this entire needle is contained in the list
	 * @param list
	 * @param needle
	 * @return
	 */
	public static boolean contains(List<Range> list, Range needle)
	{
		for (Range part:list)
		{
			long stop=part.start+part.len;
			if (part.start<=needle.start && stop>=needle.start+needle.len)
				return true;
			if (part.start>=needle.start)
				// We've passed the place in the sorted list where it would be, so we won't find it
				return false;
		}
		return false;
	}
	
	/**
	 * Returns whether the needle is inside this parent range
	 * @param parent
	 * @param needle
	 * @return
	 */
	public static boolean contains(Range parent, Range needle)
	{
		long stop=parent.start+parent.len;
		return (parent.start<=needle.start && stop>=needle.start+needle.len);
	}
	
	/**
	 * Determines whether any part of this needle touches this list
	 * @param list
	 * @param needle
	 * @return
	 */
	public static boolean containsPartial(List<Range> list, Range needle)
	{
		for (Range part:list)
		{
			long stop=part.start+part.len;
			if (part.start<=needle.start && stop>needle.start)
				return true;
			if (part.start<needle.start+needle.len && stop>needle.start+needle.len)
				return true;
			if (part.start>=needle.start+needle.len)
				// We've passed the place in the sorted list where it would be, so we won't find it
				return false;
		}
		return false;
	}
	
	public static boolean containsPartial(Range parent, Range needle)
	{
		long stop=parent.start+parent.len;
		if (parent.start<=needle.start && stop>needle.start)
			return true;
		if (parent.start<needle.start+needle.len && stop>needle.start+needle.len)
			return true;
		if (parent.start>=needle.start+needle.len)
			// We've passed the place in the sorted list where it would be, so we won't find it
			return false;
		return false;
	}
	
	/**
	 * Removes any trace of clip from the list
	 * @param list
	 * @param clip
	 * @return
	 */
	public static List<Range> remove(List<Range> list, Range clip)
	{
		List<Range> ret=new LinkedList<Range>();
		Range temp;
		for (Range part:list)
		{
			long stop=part.start+part.len;
			if (stop<part.start)
				ret.add(part);
			else if (part.start<=clip.start)		// part extends before clip, clip the middle or the end
			{
				temp=new Range();
				temp.start=part.start;
				temp.len=clip.start-part.start;
				if (temp.len>0)
					ret.add(temp);
				
				temp=new Range();
				temp.start=clip.start+clip.len;
				temp.len=stop-(clip.start+clip.len);
				if (temp.len>0)
					ret.add(temp);
			}
			else if (part.start>=clip.start && clip.start+clip.len<=stop)		// part extends after clip, clip the beginning or middle
			{
				temp=new Range();
				temp.start=clip.start+clip.len;
				temp.len=stop-(clip.start+clip.len);
				if (temp.len>0)
					ret.add(temp);
			}
			else if (part.start>=clip.start+clip.len)
				ret.add(part);
		}
		return ret;
	}
}
